KNN - ideia

• Relembrando: \(Y = r(\mathbf{X}) + \varepsilon\)
  • A relação sistemática entre \(\mathbf{X}\) e \(Y\) é “bem comportada”: \(\mathbf{X}\)’s próximos \(\Rightarrow\) \(Y\)’s semelhantes
• Usar essa ideia para criar um estimador \(g\)
• “Diga-me com quem andas e te direi quem és”

KNN - formalização

\[g(\mathbf{x}) = \mathrm{moda}_{i \in \mathcal{N}_{\mathbf{x}}^{(k)}} y_i,\] onde \(\mathcal{N}_{\mathbf{x}}^{(k)}\) é o conjunto dos índices das \(k\) observações mais próximas de \(\mathbf{x}\), ou seja, \[\mathcal{N}_{\mathbf{x}}^{(k)} = \left\{i \in \{1, \dots, n\} ~ \left| ~ d(\mathbf{x}_i, \mathbf{x}) \leq d_{\mathbf{x}}^k \right\}\right.,\] e \(d_{\mathbf{x}}^k\) representa a distância do \(k\)-ésimo vizinho mais próximo de \(\mathbf{x}\) para \(\mathbf{x}\).

KNN - propriedades

• Hiperparâmetro \(k\) \(\Rightarrow\) validação cruzada
• \(k\) alto \(\Rightarrow\) modelo simples
  • \(k \to \infty\) \(\Rightarrow\) \(g\) simples (linear?)
  • Viés alto, baixa variância
• \(k\) pequeno \(\Rightarrow\) modelo mais complexo
  • Variância alta, viés baixo
  • Requer mais dados para ser mais fidedigno

KNN - Exemplo

KNN - Exemplo

scikit-learn - KNeighborClassifier

KNN = KNeighborsClassifier(n_neighbors = 1)
KNN.fit(X_train, y_train);

KNN - Exemplo

KNN = KNeighborsClassifier(n_neighbors = 5)
KNN.fit(X_train, y_train);

KNN - Exemplo

KNN = KNeighborsClassifier(n_neighbors = 50)
KNN.fit(X_train, y_train);

KNN - Exemplo

KNN = KNeighborsClassifier(n_neighbors = 300)
KNN.fit(X_train, y_train);

KNN - Observações

• Hiperparâmetros podem (e devem!) ser otimizados através de validação cruzada
• Classificador naturalmente multiclasse
• Distâncias em alta dimensão podem impactar seu desempenho

Formalizando

• Partição do espaço das covariáveis
  • Regiões \(R_1, \dots, R_j\) distintas disjuntas
  • A predição para a resposta \(Y\) de uma observação \(\mathbf{x}\) que está na região \(k\) é a moda das respostas cujos respectivos \(\mathbf{x}\) também estão nessa região: \[g(\mathbf{x}) = \mathrm{moda}_{\{i ~ | ~ \mathbf{x}_i \in R_k\}} y_i\]

Criação da árvore

• Métricas para determinar uma nova região \(R\):
  • Erro de classificação: \(\displaystyle E = 1 - \max_{c} \hat{p}_{R, c}\)
  • Índice de Gini: \(\displaystyle G = \sum_R\sum_{c \in \mathcal{C}} \hat{p}_{R, c}(1 - \hat{p}_{R, c})\)
  • Entropia: \(\displaystyle D = -\sum_{c \in \mathcal{C}} \hat{p}_{R, c}\log(\hat{p}_{R, c})\)
• \(\hat{p}_{R, c}\) é a proporção de observações classificadas como sendo da classe \(c\) entre as que caem na região \(R\)
• Prezar por árvores puras: cada folha contém observações de somente uma única classe

Árvores de classificação - Observações

• Hiperparâmetros podem (e devem!) ser otimizados através de validação cruzada
• Classificador naturalmente multiclasse
• Poda análoga a árvores de regressão
• Podem ser acopladas em bagging
• Podem ser acopladas em florestas aleatórias

Árvores de classificação - Exemplo

Árvores de classificação - Exemplo

scikit-learn - DecisionTreeClassifier

DTC = DecisionTreeClassifier(max_depth = None, min_samples_leaf = 5)
DTC.fit(X_train, y_train);